package arithmetic1.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/*
    快速排序
 */
public class QuickSort2 {
    public static void main(String[] args) {
//        int arr[]={8,8,7,43,5,1,67,8};
        int arr[]=new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i]= (int) (Math.random()*1000000);
        }

        Date date=new Date();
        SimpleDateFormat sdf=new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String time1 = sdf.format(date);
        System.out.println("排序前的时间:"+time1);


        quickSort(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));
        date=new Date();
        String time2=sdf.format(date);
        System.out.println("排序后的时间:"+time2);
    }

    //快速排序
    public static void quickSort(int arr[],int start,int end){
        if(end-start<=0){
            return;
        }
        //将该数组划分为两个子序列
        int i = partition(arr, start, end);
        //对两个子序列再进行相同的操作
        quickSort(arr,start,i-1);
        quickSort(arr,i+1,end);
    }

    //划分算法
    public static int partition(int arr[],int start,int end){
        int i=start;
        int j=end;
        //以数组的第一个元素为基准划分
        int value=arr[start];
        while (i<j){
            //从右向左扫描小于基准的数
            while (j>i && arr[j]>=value){
                j--;
            }
            //将这个数放到前面
            arr[i]=arr[j];
            //从左到右扫描大于基准的数
            while (i<j && arr[i]<=value){
                i++;
            }
            arr[j]=arr[i];
        }
        //将temp放在中间
        arr[i]=value;
        return i;
    }
}
